from typing import List
from collections import Counter


class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        def convert(word):
            cnt = Counter(word)
            return cnt['0'], cnt['1']

        strs, size, record = [convert(word) for word in strs], len(strs), dict()

        def dfs(start, m, n):
            # 递归终止条件
            if start == size:
                return 0

            if (start, m, n) not in record:
                ans = 0
                zeros, ones = strs[start]
                # 都深度优先遍历了，里面就别 for 了哦
                if zeros <= m and ones <= n:
                    # 选择 strs[start]
                    ans = dfs(start + 1, m - zeros, n - ones) + 1
                # 不选 strs[start]
                ans = max(ans, dfs(start + 1, m, n))
                record[(start, m, n)] = ans

            return record[(start, m, n)]

        return dfs(0, m, n)


if __name__ == '__main__':
    solution = Solution()

    strs = ["1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1",
            "0", "1",
            "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0",
            "1", "0",
            "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1",
            "0", "1",
            "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0",
            "1", "0",
            "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1",
            "0", "1",
            "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0",
            "1", "0",
            "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1",
            "0", "1",
            "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0",
            "1", "0",
            "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1",
            "0", "1",
            "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0"]
    m = 30
    n = 30

    res = solution.findMaxForm(strs, m, n)
    print(res)
